{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stickers to Spell Word"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #string #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #字符串 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minStickers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #贴纸拼词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们有 <code>n</code> 种不同的贴纸。每个贴纸上都有一个小写的英文单词。</p>\n",
    "\n",
    "<p>您想要拼写出给定的字符串 <code>target</code>&nbsp;，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。</p>\n",
    "\n",
    "<p>返回你需要拼出 <code>target</code>&nbsp;的最小贴纸数量。如果任务不可能，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong>在所有的测试用例中，所有的单词都是从 <code>1000</code> 个最常见的美国英语单词中随机选择的，并且 <code>target</code>&nbsp;被选择为两个随机单词的连接。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> stickers = [\"with\",\"example\",\"science\"], target = \"thehat\"\n",
    "<b>输出：</b>3\n",
    "<strong>解释：\n",
    "</strong>我们可以使用 2 个 \"with\" 贴纸，和 1 个 \"example\" 贴纸。\n",
    "把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。\n",
    "此外，这是形成目标字符串所需的最小贴纸数量。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>stickers = [\"notice\",\"possible\"], target = \"basicbasic\"\n",
    "<b>输出：</b>-1\n",
    "<strong>解释：</strong>我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == stickers.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= stickers[i].length &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= target.length &lt;= 15</code></li>\n",
    "\t<li><code>stickers[i]</code>&nbsp;和&nbsp;<code>target</code>&nbsp;由小写英文单词组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stickers-to-spell-word](https://leetcode.cn/problems/stickers-to-spell-word/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stickers-to-spell-word](https://leetcode.cn/problems/stickers-to-spell-word/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"with\",\"example\",\"science\"]\\n\"thehat\"', '[\"notice\",\"possible\"]\\n\"basicbasic\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        if set(target).difference(set(''.join(stickers))):\n",
    "            return -1\n",
    "        \n",
    "        cands = [dict(Counter(x)) for x in stickers]\n",
    "        cnt_target = dict(Counter(target))\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(t):\n",
    "            if not t:\n",
    "                return 0\n",
    "            ans = float('inf')\n",
    "            t_cnt = dict(Counter(t))\n",
    "            for i in range(len(cands)):\n",
    "                if all(cands[i].get(x, 0) == 0 for x in t_cnt): continue\n",
    "                tmp = ''.join([x * (t_cnt.get(x, 0) - cands[i].get(x, 0)) for x in t_cnt])\n",
    "                ans = min(ans, 1 + dp(tmp))\n",
    "            return ans\n",
    "                \n",
    "        ans = dp(\"\".join(sorted(target)))\n",
    "        return ans if ans < float('inf') else -1\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers, target):\n",
    "        \"\"\"\n",
    "        :type stickers: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(target)\n",
    "        m = 1 << n\n",
    "        dp = [float('inf')]*m\n",
    "        dp[0] = 0\n",
    "        for i in range(m):\n",
    "            if dp[i] == float('inf'): continue\n",
    "            for sticker in stickers:\n",
    "                cur = i\n",
    "                for c in sticker:\n",
    "                    for k in range(n):\n",
    "                        if target[k] == c and not ((cur>>k)&1):\n",
    "                            cur |= 1<<k\n",
    "                            break\n",
    "                dp[cur] = min(dp[cur], dp[i]+1)\n",
    "        return -1 if dp[m-1] == float('inf') else dp[m-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mask = [1<<(i*5) for i in range(15)]\n",
    "clip = [(1<<((i+1)*5))-(1<<(i*5)) for i in range(15)]\n",
    "cntarr = lambda s, ct: [s.count(i) for i in ct]\n",
    "makegmask = lambda cnt: [i*j for i,j in zip(cnt, mask[:len(cnt)])]\n",
    "def applymask(d, mask):\n",
    "    for i in range(len(mask)):\n",
    "        dp = d & clip[i]\n",
    "        if dp>mask[i]: dp = mask[i]\n",
    "        d = (d & ~clip[i]) | dp\n",
    "    return d\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def minStickers(self, stickers, target):\n",
    "        \"\"\"\n",
    "        :type stickers: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        chartab = set(target)\n",
    "        targetcnt = cntarr(target, chartab)\n",
    "        gmask = makegmask(targetcnt)\n",
    "        states = {0:0}\n",
    "        for i in stickers:\n",
    "            cnti = cntarr(i, chartab)\n",
    "            gmi = sum(makegmask(cnti))\n",
    "            extras = deque()\n",
    "            for i in sorted(states.keys()):\n",
    "                ns = applymask(i+gmi, gmask)\n",
    "                if ns not in states or states[i]+1<states[ns]:\n",
    "                    states[ns] = states[i]+1\n",
    "                    extras.append(ns)\n",
    "            while extras:\n",
    "                i = extras.popleft()\n",
    "                ns = applymask(i+gmi, gmask)\n",
    "                if ns not in states or states[i]+1<states[ns]:\n",
    "                    states[ns] = states[i]+1\n",
    "                    extras.append(ns)\n",
    "            #print(states)\n",
    "        sg = sum(gmask)\n",
    "        if sg in states:\n",
    "            print(states[sg])\n",
    "            return states[sg]\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers, target):\n",
    "        \"\"\"\n",
    "        :type stickers: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(target)\n",
    "        m = 1<<n\n",
    "        dp = [float('inf') for _ in range(m)]\n",
    "        dp[0] = 0\n",
    "        for i in range(m):\n",
    "            if dp[i]==float('inf'):\n",
    "                continue\n",
    "            for s in stickers:\n",
    "                sup = i\n",
    "                for c in s:\n",
    "                    for r in range(n):\n",
    "                        if target[r] == c and ((sup>>r) & 1)==0:\n",
    "                            sup |= 1<<r\n",
    "                            break\n",
    "                dp[sup] = min(dp[sup],dp[i]+1)\n",
    "        return dp[m-1] if dp[m-1] != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: 'List[str]', target: 'str') -> 'int':\n",
    "        pos = {v:i for i,v in enumerate(set(target))}\n",
    "        N = len(pos)\n",
    "        def helper(s):\n",
    "            t = [0] * N\n",
    "            for c in s:\n",
    "                if c in pos:t[pos[c]] += 1\n",
    "            return tuple(t)\n",
    "        target = helper(target)\n",
    "        stickers = [ helper(s) for s in stickers ]\n",
    "        if any( max(a) == 0 for a in zip(*stickers) ):return -1\n",
    "        dp = {}\n",
    "        #print(target,stickers)\n",
    "        def search(s):\n",
    "            if max(s) == 0:return 0\n",
    "            if s in dp: return dp[s]\n",
    "            idx = s.index(max(s))\n",
    "            dp[s] =  min( search(tuple( s[i] - t[i] if s[i] > t[i] else 0 for i in range(N) )) for t in stickers if t[idx] > 0 ) + 1\n",
    "            return dp[s]\n",
    "        return search(target)\n",
    "        #print(len(dp))\n",
    "        #print(dp)\n",
    "        #print(dp[target])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter \n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        t_count = Counter(target)\n",
    "        A = [Counter(sticker) & t_count for sticker in stickers]\n",
    "\n",
    "        for i in range(len(A)-1, -1, -1):\n",
    "            if any(A[i] == A[i] & A[j] for j in range(len(A)) if i != j):\n",
    "                A.pop(i)\n",
    "\n",
    "        stickers = [\"\".join(s_count.elements()) for s_count in A]\n",
    "\n",
    "        dp = [-1] * (1 << len(target))\n",
    "        dp[0] = 0\n",
    "\n",
    "        for state in range(1 << len(target)):\n",
    "            if dp[state] == -1: continue\n",
    "\n",
    "            for sticker in stickers:\n",
    "                now = state\n",
    "                for letter in sticker:\n",
    "                    for i, c in enumerate(target):\n",
    "                        if (now >> i) & 1:\n",
    "                            continue\n",
    "                        if c == letter:\n",
    "                            now |= 1 << i\n",
    "                            break\n",
    "                if dp[now] == -1 or dp[now] > dp[state] + 1:\n",
    "                    dp[now] = dp[state] + 1\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        from collections import Counter\n",
    "        import functools\n",
    "        stickers = [Counter(s) for s in stickers]\n",
    "        #lookup = {}\n",
    "        @functools.lru_cache(None)\n",
    "        def helper(target):\n",
    "            if not target: return 0\n",
    "            #if target in lookup: return lookup[target]\n",
    "            res, cnt = float(\"inf\"), Counter(target)\n",
    "            for c in stickers:\n",
    "                if c[target[-1]] == 0:continue\n",
    "                nxt = helper(\"\".join([s * t for (s, t) in (cnt - c).items()]))\n",
    "                if nxt != -1: res = min(res, nxt + 1)\n",
    "            #lookup[target] = -1 if res == float(\"inf\") else res\n",
    "            return -1 if res == float(\"inf\") else res\n",
    "        return helper(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        m = len(stickers)\n",
    "        mp = [[0] * 26 for y in range(m)]\n",
    "        for i in range(m):\n",
    "            for c in stickers[i]:\n",
    "                mp[i][ord(c) - ord('a')] += 1\n",
    "        dp = {}\n",
    "        dp[\"\"] = 0\n",
    "\n",
    "        def helper(dp, mp, target):\n",
    "            if target in dp:\n",
    "                return dp[target]\n",
    "            n = len(mp)\n",
    "            tar = [0] * 26\n",
    "            for c in target:\n",
    "                tar[ord(c) - ord('a')] += 1\n",
    "            ans = sys.maxsize\n",
    "            for i in range(n):\n",
    "                if mp[i][ord(target[0]) - ord('a')] == 0:\n",
    "                    continue\n",
    "                s = ''\n",
    "                for j in range(26):\n",
    "                    if tar[j] > mp[i][j]:\n",
    "                        s += chr(ord('a') + j) * (tar[j] - mp[i][j])\n",
    "                tmp = helper(dp, mp, s)\n",
    "                if (tmp != -1):\n",
    "                    ans = min(ans, 1 + tmp)\n",
    "            dp[target] = -1 if ans == sys.maxsize else ans\n",
    "            return dp[target]\n",
    "\n",
    "        return helper(dp, mp, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        n,m = len(stickers),len(target)\n",
    "        f = [float('inf')]*(1<<m)\n",
    "        cnt = [[0]*26 for _ in range(n)]\n",
    "        can = [[] for _ in range(26)]#包含字母ch的sticker的序列\n",
    "        for i in range(n):\n",
    "            for ch in stickers[i]:\n",
    "                idx = ord(ch)-ord('a')\n",
    "                cnt[i][idx]+=1\n",
    "                if can[idx]==[] or can[idx][-1]!=i:\n",
    "                    can[idx].append(i)\n",
    "\n",
    "        f[0] = 0\n",
    "        for cur in range(1<<m):\n",
    "            if f[cur]==float('inf'):continue\n",
    "            # 对于状态i中还是0的位 我们遍历一遍stickers[k]只要能填target[i]字符串 就填上 作为i能到达的一种ne状态\n",
    "            # 找第一个当前状态是0的字符串 target[d]对应的那些包含target[d]的stiker的下标数组can[d]---从而确保状态10 -> 11 和 01 -> 11的重复情况不出现\n",
    "            d = 0\n",
    "            for j in range(m):\n",
    "                if not cur&(1<<j):\n",
    "                    d = j\n",
    "                    break\n",
    "            d = ord(target[d])-ord('a')\n",
    "            \n",
    "            for k in can[d]:\n",
    "                ne = cur\n",
    "                tmp = cnt[k][:]#创建一个临时统计量\n",
    "                # 遍历target每一位j\n",
    "                for j in range(m):\n",
    "                    # 已经填好了的位不用管\n",
    "                    if ne&(1<<j):continue\n",
    "                    # 如果stickers[k]还有字符串target[j]可填\n",
    "                    if tmp[ord(target[j])-ord('a')]>0:\n",
    "                        ne|=(1<<j)\n",
    "                        tmp[ord(target[j])-ord('a')]-=1\n",
    "                f[ne] = min(f[ne],f[cur]+1)\n",
    "        return f[(1<<m)-1] if f[(1<<m)-1]!=float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        a = ord('a')\n",
    "        tar = [0] * 26\n",
    "        for c in target:\n",
    "            tar[ord(c) - a] += 1\n",
    "        iters = []\n",
    "        for i in range(26):\n",
    "            if tar[i]:\n",
    "                iters.append(i)\n",
    "        words = []\n",
    "        for st in stickers:\n",
    "            word = [0] * 26\n",
    "            for i in iters:\n",
    "                word[i] = st.count(chr(i + a))\n",
    "            for i in iters:\n",
    "                if word[i]:\n",
    "                    words.append(word)\n",
    "                    break\n",
    "        maxns = []\n",
    "        for word in words:\n",
    "            maxn = 0\n",
    "            for i in iters:\n",
    "                if word[i]:\n",
    "                    c = 0\n",
    "                    if tar[i] % word[i]:\n",
    "                        c = 1\n",
    "                    t = tar[i] // word[i] + c\n",
    "                    if t > maxn: maxn = t\n",
    "            maxns.append(maxn)\n",
    "        mx = [[0] * 26]; mxix = 1; dic = {0:0}\n",
    "        mxn = [0]\n",
    "        toupdates = []\n",
    "        def cal(temp, n):\n",
    "            nonlocal mxix, toupdates\n",
    "            k = 1; ix = 0\n",
    "            for i in iters:\n",
    "                ix += temp[i] * k\n",
    "                k *= 14\n",
    "            if ix in dic:\n",
    "                ix = dic[ix]\n",
    "                toupdates.append((ix, n))\n",
    "                return ix\n",
    "            else:\n",
    "                dic[ix] = mxix\n",
    "                mx.append(temp)\n",
    "                mxn.append(n)\n",
    "                mxix += 1\n",
    "                return mxix - 1\n",
    "        cal(tar, 16)\n",
    "        maxnsix = 0\n",
    "        for word in words:\n",
    "            tword = [0] * 26\n",
    "            presize = mxix\n",
    "            toupdates = []\n",
    "            for times in range(1, maxns[maxnsix] + 1):\n",
    "                mxn1_times = mxn[1] - times\n",
    "                for i in iters:\n",
    "                    tword[i] += word[i]\n",
    "                for p in range(presize):\n",
    "                    if mxn[p] >= mxn1_times:\n",
    "                        continue\n",
    "                    temp = [0] * 26\n",
    "                    for i in iters:\n",
    "                        temp[i] = tword[i] + mx[p][i]\n",
    "                        if temp[i] > tar[i]:\n",
    "                            temp[i] = tar[i]\n",
    "                    cal(temp, times + mxn[p])\n",
    "            for ix, n in toupdates:\n",
    "                if n < mxn[ix]:\n",
    "                    mxn[ix] = n\n",
    "            maxnsix += 1\n",
    "        res = mxn[cal(tar, 0)]\n",
    "        if res == 16: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        def trans(s):\n",
    "            counter = collections.Counter()\n",
    "            for c in s:\n",
    "                if c in target:\n",
    "                    counter[c] += 1\n",
    "            return counter\n",
    "\n",
    "        counters = [c for st in stickers if (c:=trans(st))]\n",
    "        queue = [(target, 0)]\n",
    "        seen= {target}\n",
    "\n",
    "        while queue:\n",
    "            cur, step = queue.pop(0)\n",
    "            if not cur:\n",
    "                return step\n",
    "\n",
    "            for counter in counters:\n",
    "                if cur[0] in counter:\n",
    "                    nextCur = cur\n",
    "                    for c, cnt in counter.items():\n",
    "                        nextCur = nextCur.replace(c, \"\",cnt)\n",
    "                    if nextCur not in seen:\n",
    "                        seen.add(nextCur)\n",
    "                        queue.append((nextCur, step + 1))\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "# 实际上就是把每个状态看作一个节点，\n",
    "# 从target开始进行bfs，\n",
    "# 每条边代表选择一个sticker进行消除，\n",
    "# 然后得出下一个节点，\n",
    "# 最后一旦碰到空节点，\n",
    "# 根据bfs的特性，第一次访问到节点的路径最短，于是可以作为答案直接返回\n",
    "# bfs\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "#         def trans(s):\n",
    "#             counter = collections.Counter()\n",
    "#             for c in s:\n",
    "#                 if c in target:\n",
    "#                     counter[c] += 1\n",
    "#             return counter\n",
    "        \n",
    "#         counters = [ c for st in stickers if (c := trans(st)) ]\n",
    "#         queue = [(target, int(0))]\n",
    "#         seen = {target}\n",
    "#         while queue:\n",
    "#             cur, step = queue.pop(0)\n",
    "#             if not cur:\n",
    "#                 return step\n",
    "\n",
    "#             for counter in counters:\n",
    "#                 if cur[0] in counter:\n",
    "#                     nextCur = cur\n",
    "#                     for c, cnt in counter.items():\n",
    "#                         nextCur = nextCur.replace(c, \"\", cnt)\n",
    "\n",
    "#                     if nextCur not in seen:\n",
    "#                         seen.add(nextCur)\n",
    "#                         queue.append((nextCur, step + 1))\n",
    "#         return -1\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "#         def trans(s):\n",
    "#             cnts = collections.Counter()\n",
    "#             for c in s:\n",
    "#                 if c in target:\n",
    "#                     cnts[c] += 1\n",
    "#             return cnts\n",
    "#         availables = [c for st in stickers if (c:=trans(st))]\n",
    "#         print(availables[0])\n",
    "#         queue = collections.deque([(target, int(0))])\n",
    "#         explored = {target}\n",
    "#         while queue:\n",
    "#             cur, step = queue.popleft()\n",
    "#             if not cur:\n",
    "#                 return step\n",
    "#             for avl in availables:\n",
    "#                 if cur[0] in avl:\n",
    "#                     nxt = cur\n",
    "#                     for k, v in avl.items():\n",
    "#                         print(nxt)\n",
    "#                         nxt = nxt.replace(k, '', v)\n",
    "#                         print(\"--\", nxt)\n",
    "#                     if nxt not in explored:\n",
    "#                         explored.add(nxt)\n",
    "#                         queue.append((nxt, step + 1))\n",
    "#         return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        def trans(s):\n",
    "            cnts = Counter()\n",
    "            for c in s:\n",
    "                if c in target:\n",
    "                    cnts[c] += 1\n",
    "            return cnts\n",
    "\n",
    "        availables = [c for st in stickers if (c:=trans(st))]\n",
    "        queue = deque([(target, 0)])\n",
    "        explored = {target}\n",
    "        while queue:\n",
    "            cur, step = queue.popleft()\n",
    "            if not cur:\n",
    "                return step\n",
    "            for avl in availables:\n",
    "                if cur[0] in avl:\n",
    "                    nxt = cur\n",
    "                    for k, v in avl.items():\n",
    "                        nxt = nxt.replace(k, '', v)\n",
    "                    if nxt not in explored:\n",
    "                        explored.add(nxt)\n",
    "                        queue.append((nxt, step + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        dic = {}\n",
    "        for i in target:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        flag = []\n",
    "        count = 0\n",
    "        f = {}\n",
    "        target=0\n",
    "        for i in dic:\n",
    "            f[i] = len(flag)\n",
    "            target+=dic[i]*pow(2,count)\n",
    "            flag.append([count, dic[i]+count])\n",
    "            count += dic[i]\n",
    "        flag1 = []\n",
    "        for i in range(len(flag)):\n",
    "            flag1.append(pow(2, count) - 1 - sum([pow(2, j) for j in range(flag[i][0], flag[i][1])]))\n",
    "        for i in range(len(stickers)):\n",
    "            dic1 = {}\n",
    "            for j in stickers[i]:\n",
    "                if j in dic:\n",
    "                    if j in dic1:\n",
    "                        dic1[j] += 1\n",
    "                    else:\n",
    "                        dic1[j] = 1\n",
    "            stickers[i] = [[dic1[j] * pow(2, flag[f[j]][0]),flag1[f[j]]] for j in dic1]\n",
    "        dp=[inf]*(target+1)\n",
    "        for i in range(len(stickers)):\n",
    "            dp1 = dp[:]\n",
    "            dp[0]=0\n",
    "            for j in range(1,target+1):\n",
    "                num = j\n",
    "                for k in stickers[i]:\n",
    "                    num=max(num-k[0],num&k[1])\n",
    "                dp[j] = min(dp1[j],dp[num]+1)\n",
    "        return dp[-1] if dp[-1]!=inf else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        def trans(s):\n",
    "            cnts = Counter()\n",
    "            for c in s:\n",
    "                if c in target:\n",
    "                    cnts[c] += 1\n",
    "            return cnts\n",
    "\n",
    "        # availables = [c for st in stickers if (c:=trans(st))]\n",
    "        # print(availables)\n",
    "        availables = []\n",
    "\n",
    "        for st in stickers:\n",
    "            c_counter = trans(st)\n",
    "            if c_counter:\n",
    "                availables.append(c_counter)\n",
    "        \n",
    "        q = deque([])\n",
    "        q.append(target)\n",
    "        visited = set()\n",
    "        visited.add(target)\n",
    "        step = 0\n",
    "        \n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                cur_str = q.popleft()\n",
    "\n",
    "                if not cur_str:\n",
    "                    return step \n",
    "                \n",
    "                for ava in availables:\n",
    "                    if cur_str[0] in ava:\n",
    "                        reduce_str = cur_str\n",
    "                        for k, v in ava.items():\n",
    "                            reduce_str = reduce_str.replace(k, \"\", v)\n",
    "                        \n",
    "                        if reduce_str in visited:\n",
    "                            continue \n",
    "                        visited.add(reduce_str)\n",
    "                        q.append(reduce_str)\n",
    "\n",
    "                # print(q)\n",
    "                # print(visited)\n",
    "                \n",
    "                # print(step)\n",
    "            step += 1 \n",
    "        \n",
    "        return -1 \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        len_target = len(target) # 目标字符串的长度\n",
    "        mask = 1 << len_target # 用位掩码表示所有可能的状态，共有 2^m 种状态\n",
    "        INF = 20  # 题目中 target < 15\n",
    "        dp = [INF] * mask  # 动态规划数组，f[state] 表示达到状态 state 所需的最小贴纸数量\n",
    "        dp[0] = 0  # 初始状态（没有任何字符匹配）所需的贴纸数量为 0\n",
    "        # 遍历所有可能的状态\n",
    "        for state in range(mask):\n",
    "            if dp[state] == INF: continue\n",
    "            # 尝试使用每一张贴纸\n",
    "            for sticker in stickers:\n",
    "                new_state = state\n",
    "                # 遍历贴纸上的每一个字符\n",
    "                for char in sticker:\n",
    "                    for i in range(len_target):\n",
    "                    # 如果贴纸上的字符可以匹配目标字符串中的字符，并且该字符尚未被匹配\n",
    "                        if char == target[i] and ((new_state >> i) & 1) == 0:\n",
    "                            new_state |= (1 << i) # 更新状态，表示该字符已被匹配\n",
    "                            break # 匹配成功后，跳出循环，继续尝试下一个字符\n",
    "                # 更新达到新状态 ns 所需的最小贴纸数量\n",
    "                dp[new_state] = min(dp[new_state], dp[state] + 1)\n",
    "        # 返回达到所有字符都匹配的状态所需的最小贴纸数量\n",
    "        return -1 if dp[mask - 1] == INF else dp[mask - 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "\n",
    "        def transform(s):\n",
    "            cnt = Counter()\n",
    "            for c in s:\n",
    "                if c in target:\n",
    "                    cnt[c] += 1\n",
    "            return cnt\n",
    "\n",
    "        n_stickers = [c for s in stickers if (c:=transform(s))]\n",
    "        seen = {target}\n",
    "        min_step = float('inf')\n",
    "\n",
    "        @cache\n",
    "        def dfs(rem, step):\n",
    "            nonlocal min_step\n",
    "\n",
    "            if not rem:\n",
    "                min_step = min(min_step, step)\n",
    "                return\n",
    "\n",
    "            for st in n_stickers:\n",
    "                if rem[0] in st:\n",
    "                    new_rem = ''.join(k * v for k, v in (Counter(rem) - st).items())\n",
    "                    dfs(new_rem, step + 1)\n",
    "            \n",
    "\n",
    "        dfs(target, 0)\n",
    "        if min_step != float('inf'):\n",
    "            return min_step            \n",
    "\n",
    "        return -1\n",
    "\n",
    "        # q = [(target, 0)]\n",
    "        # seen = {target}\n",
    "\n",
    "        # while q:\n",
    "        #     rem, step = q.pop(0)\n",
    "        #     if not rem:\n",
    "        #         return step\n",
    "\n",
    "        #     for st in n_stickers:\n",
    "        #         if rem[0] in st:\n",
    "        #             new_rem = rem\n",
    "        #             for k, v in st.items():\n",
    "        #                 new_rem = new_rem.replace(k, '', v)\n",
    "        #             if new_rem not in seen:\n",
    "        #                 seen.add(new_rem)\n",
    "        #                 q.append((new_rem, step + 1))\n",
    "\n",
    "        # return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        m = len(target)\n",
    "        d = defaultdict(list)\n",
    "        for i, x in enumerate(target):\n",
    "            d[x].append(i)\n",
    "        @cache\n",
    "        def dp(mask: int) -> int:\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for sticker in stickers: # 枚举选哪个\n",
    "                left = mask\n",
    "                for x in sticker:\n",
    "                    for i in d[x]:\n",
    "                        if left >> i & 1:\n",
    "                            left ^= 1 << i\n",
    "                            break\n",
    "                # for x in sticker:\n",
    "                #     for i, c in enumerate(target):\n",
    "                #         if left >> i & 1 and x == c:\n",
    "                #             left ^= 1 << i\n",
    "                #             break\n",
    "                # cnt = Counter(sticker)\n",
    "                # for i, c in enumerate(target):\n",
    "                #     if left >> i & 1 and cnt[c]:\n",
    "                #         cnt[c] -= 1\n",
    "                #         left ^= 1 << i\n",
    "                if left != mask:\n",
    "                    res = min(res, dp(left) + 1)\n",
    "            return res\n",
    "        res = dp((1 << m) - 1)\n",
    "        return res if res < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#贴纸拼词，状压dp，记忆化搜索。输入： stickers = [\"with\",\"example\",\"science\"], target = \"thehat\"，输出：3\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        m = len(target)\n",
    "        @functools.lru_cache(None)\n",
    "        def dp(mask: int) -> int:\n",
    "            if mask == 0:return 0\n",
    "            res = m + 1\n",
    "            for sticker in stickers:\n",
    "                left = mask\n",
    "                cnt = Counter(sticker)\n",
    "                for i, c in enumerate(target):\n",
    "                    if mask >> i & 1 and cnt[c]:\n",
    "                        cnt[c] -= 1\n",
    "                        left ^= 1 << i\n",
    "                if left < mask:\n",
    "                    res = min(res, dp(left) + 1)\n",
    "            return res\n",
    "        res = dp((1 << m) - 1)\n",
    "        return res if res <= m else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        tmp = [0 for _ in range(26)]\n",
    "        for l in target: tmp[ord(l) - ord('a')] += 1\n",
    "        n = len(stickers)\n",
    "        cnts = [[0 for _ in range(26)] for _ in range(n)]\n",
    "        for i, word in enumerate(stickers):\n",
    "            for l in word: cnts[i][ord(l) - ord('a')] += 1\n",
    "        for i in range(26):\n",
    "            val = 0\n",
    "            for j in range(n): val += cnts[j][i]\n",
    "            if val == 0 and tmp[i] > 0: return -1\n",
    "        tar = tuple(x for x in tmp)\n",
    "        st = tuple(0 for _ in range(26))\n",
    "        stack = []\n",
    "        heapq.heappush(stack, [0, st])\n",
    "        visited = {st: 0}\n",
    "        while stack:\n",
    "            res, st = heapq.heappop(stack)\n",
    "            if st in visited and visited[st] < res: continue\n",
    "            if st == tar: return res\n",
    "            for i in range(n):\n",
    "                tmp = []\n",
    "                for j in range(26): tmp.append(min(st[j] + cnts[i][j], tar[j]))\n",
    "                tmp1 = tuple(tmp)\n",
    "                if not tmp1 in visited or visited[tmp1] > res + 1:\n",
    "                    heapq.heappush(stack, [res + 1, tmp1])\n",
    "                    visited[tmp1] = res + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        n = len(target)\n",
    "        dp = collections.defaultdict(int)\n",
    "        s = collections.Counter(target)\n",
    "        A = [collections.Counter(stick)&s for stick in stickers]\n",
    "        for i in range(len(A)-1,-1,-1):\n",
    "            if any( A[i]&A[j]==A[i] for j in range(len(A)) if i!=j):\n",
    "                A.pop(i)\n",
    "        for i in range(1<<n):\n",
    "            if dp[i]==0 and i!=0:\n",
    "                continue\n",
    "            for a in A:\n",
    "                nex = i\n",
    "                has = a.copy()\n",
    "                for pos in range(n):\n",
    "                    if i&(1<<pos)!=0 or has[target[pos]]==0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        nex|=(1<<pos)\n",
    "                        has[target[pos]]-=1\n",
    "                if i!=nex:\n",
    "                    dp[nex] = dp[i]+1 if dp[nex]==0 else min(dp[nex],dp[i]+1)\n",
    "        return -1 if dp[(1<<n)-1]==0 else dp[(1<<n)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        n = len(target)\n",
    "        dp = collections.defaultdict(int)\n",
    "        s = collections.Counter(target)\n",
    "        A = [collections.Counter(stick)&s for stick in stickers]\n",
    "        for i in range(len(A)-1,-1,-1):\n",
    "            if any( A[i]&A[j]==A[i] for j in range(len(A)) if i!=j):\n",
    "                A.pop(i)\n",
    "        for i in range(1<<n):\n",
    "            if dp[i]==0 and i!=0:\n",
    "                continue\n",
    "            for a in A:\n",
    "                nex = i\n",
    "                has = a.copy()\n",
    "                for pos in range(n):\n",
    "                    if i&(1<<pos)!=0 or has[target[pos]]==0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        nex|=(1<<pos)\n",
    "                        has[target[pos]]-=1\n",
    "                if i!=nex:\n",
    "                    dp[nex] = dp[i]+1 if dp[nex]==0 else min(dp[nex],dp[i]+1)\n",
    "        return -1 if dp[(1<<n)-1]==0 else dp[(1<<n)-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        counter = [0] * 26\n",
    "        for c in target:\n",
    "            counter[ord(c) - ord('a')] += 1\n",
    "        \n",
    "        data = []\n",
    "        for sticker in stickers:\n",
    "            tmp_counter = [0] * 26\n",
    "            for c in sticker:\n",
    "                tmp_counter[ord(c) - ord('a')] += 1\n",
    "            data.append(tmp_counter)\n",
    "\n",
    "        @cache\n",
    "        def dfs(counter):\n",
    "            if sum(counter) == 0:\n",
    "                return 0\n",
    "            mn = inf\n",
    "            for sticker in data:\n",
    "                tmp_counter = list(counter)\n",
    "                for i, c in enumerate(sticker):\n",
    "                    tmp_counter[i] = max(0, tmp_counter[i] - c)\n",
    "                tmp_counter = tuple(tmp_counter)\n",
    "                if tmp_counter != counter:\n",
    "                    mn = min(mn, 1 + dfs(tmp_counter))\n",
    "            return mn\n",
    "                    \n",
    "        \n",
    "\n",
    "        ans = dfs(tuple(counter))\n",
    "        if ans == inf:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def dfs(self, state):\n",
    "        if state == 0:\n",
    "            return 0\n",
    "        \n",
    "        res = float('inf')\n",
    "        for sticker in self.stickers:\n",
    "            c = Counter(sticker)\n",
    "            left = state\n",
    "            for i in range(self.n):\n",
    "                if (state >> i) & 1 == 1 and c[self.target[i]]:\n",
    "                    left = left ^ (1 << i)\n",
    "                    c[self.target[i]] -= 1\n",
    "            if left < state:\n",
    "                res = min(res, self.dfs(left) + 1)\n",
    "        return res\n",
    "\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        self.stickers = stickers\n",
    "        self.target = target\n",
    "\n",
    "        self.n = len(target)\n",
    "        cnt = self.dfs((1 << self.n) - 1)\n",
    "        return -1 if cnt == float('inf') else cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        ct = collections.Counter(target)\n",
    "        cnt = collections.Counter(''.join(stickers))\n",
    "        for k, v in ct.items():\n",
    "            if k not in cnt:\n",
    "                return -1 \n",
    "        \n",
    "        mapping = collections.defaultdict(dict)\n",
    "        for word in stickers:\n",
    "            cw = collections.Counter(word)\n",
    "            for k in ct.keys():\n",
    "                if k not in cw:\n",
    "                    continue\n",
    "                mapping[word][k] = cw[k]\n",
    "        \n",
    "        memo = {}\n",
    "        def dfs(state):\n",
    "            if state in memo:\n",
    "                return memo[state]\n",
    "            if not state:\n",
    "                return 0 \n",
    "            val = sys.maxsize \n",
    "            for w in mapping:\n",
    "                ostate = dict(state)\n",
    "                flag = False \n",
    "                for k in ostate.keys():\n",
    "                    if k in mapping[w].keys():\n",
    "                        ostate[k] -= mapping[w][k]\n",
    "                        flag = True \n",
    "                if flag:\n",
    "                    nstate = {k:v for k, v in ostate.items() if v > 0}\n",
    "                    val = min(val, dfs(tuple(nstate.items())) + 1)\n",
    "            memo[state] = val \n",
    "            return val \n",
    "        return dfs(tuple(ct.items()))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        tag, cur = [0] * 26, [0] * 26\n",
    "        for s in target:\n",
    "            tag[ord(s) - ord('a')] += 1\n",
    "\n",
    "        mem = {}\n",
    "        mem[\"_\".join([str(i) for i in tag])] = 0\n",
    "\n",
    "        def dfs(acc: int) -> int:\n",
    "            nonlocal cur\n",
    "            if acc > len(target):\n",
    "                return target\n",
    "\n",
    "            key = \"_\".join([str(i) for i in cur])\n",
    "            if key in mem:\n",
    "                return mem[key]\n",
    "\n",
    "            if all([tag[i] <= cur[i] for i in range(26)]):\n",
    "                mem[key] = 0\n",
    "                return 0\n",
    "\n",
    "            mi = len(target) + 1\n",
    "            for stk in stickers:\n",
    "                contribute = False\n",
    "                cloneList = [i for i in cur]\n",
    "                for s in stk:\n",
    "                    k = ord(s) - ord('a')\n",
    "                    if cur[k] < tag[k]:\n",
    "                        contribute = True\n",
    "                        cur[k] += 1\n",
    "                if contribute:\n",
    "                    mi = min(dfs(acc + 1) + 1, mi)\n",
    "                cur = [i for i in cloneList]\n",
    "            mem[key] = mi\n",
    "            return mi\n",
    "\n",
    "        ans = dfs(0)\n",
    "        return ans if ans <= len(target) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        leftLetters = {}\n",
    "        for char in target:\n",
    "            if char not in leftLetters:\n",
    "                leftLetters[char] = 0\n",
    "            leftLetters[char] += 1\n",
    "\n",
    "        stats = {}\n",
    "        def getStatKey():\n",
    "            stats = [0] * 26\n",
    "            for char, cnt in leftLetters.items():\n",
    "                idx = ord(char) - ord('a')\n",
    "                stats[idx] = cnt\n",
    "            stats = [str(cnt) for cnt in stats]\n",
    "            return ','.join(stats)\n",
    "\n",
    "        def _solve():\n",
    "            if len(leftLetters) == 0:\n",
    "                return 0\n",
    "            \n",
    "            statKey = getStatKey()\n",
    "            if statKey in stats:\n",
    "                return stats[statKey]\n",
    "\n",
    "            minCnt = float('inf')\n",
    "            for word in stickers:\n",
    "                removed = {}\n",
    "                for char in word:\n",
    "                    if char in leftLetters:\n",
    "                        leftLetters[char] -= 1\n",
    "                        if leftLetters[char] == 0:\n",
    "                            leftLetters.pop(char)\n",
    "                        if char not in removed:\n",
    "                            removed[char] = 0\n",
    "                        removed[char] += 1\n",
    "                if removed:\n",
    "                    curMin = _solve() + 1\n",
    "                    minCnt = min(minCnt, curMin)\n",
    "                    # add back\n",
    "                    for char, cnt in removed.items():\n",
    "                        if char not in leftLetters:\n",
    "                            leftLetters[char] = 0\n",
    "                        leftLetters[char] += cnt\n",
    "            \n",
    "            stats[statKey] = minCnt\n",
    "            return minCnt\n",
    "        \n",
    "        minCnt = _solve()\n",
    "\n",
    "        return -1 if minCnt == float('inf') else minCnt\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "target\n",
    "get curBest sticker, then DFS\n",
    "\n",
    "if leftLetters is empty:\n",
    "    return 0\n",
    "\n",
    "curLetters = list(target)\n",
    "minCnt = 0\n",
    "for word in stickers:\n",
    "    cnrMin = DFS(curletters) + 1\n",
    "    remove(word, curLetters)\n",
    "    minCnt = min(minCnt,cnrMin)\n",
    "    addback(word, curLetters)\n",
    "\n",
    "return minCnt\n",
    "\n",
    "\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        target = counter(target)\n",
    "        tmp = {key for key in target}\n",
    "        stickers_counter = []\n",
    "      \n",
    "        for sticker in stickers:\n",
    "            sticker = counter(sticker, target)\n",
    "            if sticker:\n",
    "                stickers_counter.append(sticker)\n",
    "\n",
    "                # 验证是否包含所有字母\n",
    "                for alpha in sticker:\n",
    "                    if alpha in tmp:\n",
    "                        tmp.remove(alpha)\n",
    "        if tmp:\n",
    "            return -1   \n",
    "\n",
    "        # 每次使用匹配度最高的词\n",
    "        # count = 0\n",
    "        # while sum(target.values()):\n",
    "        #     count += 1\n",
    "        #     sticker = find(stickers_counter, target)\n",
    "        #     for alpha, c in sticker.items():\n",
    "        #         target[alpha] -= c\n",
    "        # return count\n",
    "\n",
    "\n",
    "        # 暴力破解\n",
    "        return find(stickers_counter, tuple(target.items()))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def counter(s, only=None):\n",
    "    count = {}\n",
    "    for v in s:\n",
    "        if only and v not in only:\n",
    "            continue\n",
    "\n",
    "        if v not in count:\n",
    "            count[v] = 1\n",
    "        else:\n",
    "            count[v] += 1\n",
    "    return count\n",
    "\n",
    "\n",
    "def find(stickers, target):\n",
    "    # 存储匹配的值\n",
    "    vals = [None] * len(stickers)\n",
    "    # 存储匹配的条数, 为排序后与vals匹配, 为(count, index)格式\n",
    "    counts = [None] * len(stickers)\n",
    "\n",
    "    for index, sticker in enumerate(stickers):\n",
    "        val = {}\n",
    "        count = 0\n",
    "        for alpha in sticker:\n",
    "            tmp = min(sticker[alpha], target[alpha])\n",
    "            val[alpha] = tmp\n",
    "            count += tmp\n",
    "        vals[index] = val\n",
    "        counts[index] = (count, index)\n",
    "\n",
    "    counts.sort()\n",
    "    return vals[counts[-1][1]]\n",
    "\n",
    "\n",
    "def find(stickers, target):\n",
    "    visited = {}\n",
    "\n",
    "    def inner(stickers, target):\n",
    "        if not target:\n",
    "            return 0\n",
    "        if target in visited:\n",
    "            return visited[target]\n",
    "\n",
    "        result = float(\"inf\")   \n",
    "        new_stickers = []     \n",
    "        targets = []\n",
    "        for sticker in stickers:\n",
    "            new_target = []\n",
    "            # 用于剔除不会提供贡献的贴纸\n",
    "            flag = False\n",
    "            for alpha, count in target:\n",
    "                if alpha in sticker:\n",
    "                    remain = count - sticker[alpha]\n",
    "                    flag = True\n",
    "                else:\n",
    "                    remain = count\n",
    "                if remain > 0:         \n",
    "                    new_target.append((alpha, remain))\n",
    "\n",
    "            # 如果该贴纸在当前节点无法提供贡献, 在更深入的节点也无法提供\n",
    "            if flag:\n",
    "                new_stickers.append(sticker)\n",
    "                targets.append(tuple(new_target))\n",
    "\n",
    "        for new_target in targets:\n",
    "            r = inner(stickers, new_target)\n",
    "            # 已找到当前路由下的最优解, 进行剪枝\n",
    "            if r == 0:\n",
    "                result = r\n",
    "                break\n",
    "            if r < result:\n",
    "                result = r\n",
    "\n",
    "        result += 1\n",
    "        visited[target] = result\n",
    "        return result\n",
    "    return inner(stickers, target)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        alphabet=set()\n",
    "        for sticker in stickers:\n",
    "            alphabet|=set(sticker)\n",
    "        for c in target:\n",
    "            if c not in alphabet:\n",
    "                return -1\n",
    "        def str2list(s):\n",
    "            ans=[0]*26\n",
    "            for c in s:\n",
    "                ans[ord(c)-ord(\"a\")]+=1\n",
    "            return tuple(ans)\n",
    "        def maxsubseq(l1,l2):\n",
    "            ans=[min(l1[i],l2[i]) for i in range(26)]\n",
    "            return tuple(ans)\n",
    "        stickerslist=[str2list(s) for s in stickers]\n",
    "        targetlist=str2list(target)\n",
    "        dp=[set() for i in range(len(target)+1)]\n",
    "        dp[0].add(targetlist)\n",
    "        i=0\n",
    "        for i in range(len(target)+1):\n",
    "            for key in dp[i]:\n",
    "                for s in stickerslist:\n",
    "                    temp=maxsubseq(key,s)\n",
    "                    newtarget=tuple(key[i]-temp[i] for i in range(26))\n",
    "                    if sum(newtarget)==0:\n",
    "                        return i+1\n",
    "                    if newtarget not in dp[i+1]:\n",
    "                        dp[i+1].add(newtarget)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, words: List[str], target: str) -> int:\n",
    "        st=set(target)\n",
    "        n=len(words)\n",
    "        count=[defaultdict(int) for _ in range(n)]\n",
    "        for i,w in enumerate(words):\n",
    "            for c in w:\n",
    "                if c in st:\n",
    "                    count[i][c]+=1\n",
    "        m=len(target)\n",
    "        @cache\n",
    "        def check(tmp):\n",
    "            cnt=defaultdict(int)\n",
    "            i=0\n",
    "            while tmp:\n",
    "                if tmp&1:\n",
    "                    cnt[target[i]]+=1\n",
    "                i+=1\n",
    "                tmp>>=1\n",
    "            for i in range(n):\n",
    "                flag=True\n",
    "                for c in cnt.keys():\n",
    "                    if count[i][c]<cnt[c]:\n",
    "                        flag=False\n",
    "                        break\n",
    "                if flag:\n",
    "                    break\n",
    "            return flag\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            if state==0:\n",
    "                return 0\n",
    "            else:\n",
    "                res=float(\"inf\")\n",
    "                sub=state\n",
    "                while sub:\n",
    "                    sub=(sub-1)&state\n",
    "                    tmp=state^sub\n",
    "                    if check(tmp):\n",
    "                        res=min(res,dfs(sub)+1)\n",
    "                return res\n",
    "        res=dfs((1<<m)-1) \n",
    "        return -1 if res==float(\"inf\") else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, words: List[str], target: str) -> int:\n",
    "        st=set(target)\n",
    "        n=len(words)\n",
    "        count=[defaultdict(int) for _ in range(n)]\n",
    "        for i,w in enumerate(words):\n",
    "            for c in w:\n",
    "                if c in st:\n",
    "                    count[i][c]+=1\n",
    "        m=len(target)\n",
    "        @cache\n",
    "        def check(tmp):\n",
    "            cnt=defaultdict(int)\n",
    "            i=0\n",
    "            while tmp:\n",
    "                if tmp&1:\n",
    "                    cnt[target[i]]+=1\n",
    "                i+=1\n",
    "                tmp>>=1\n",
    "            for i in range(n):\n",
    "                flag=True\n",
    "                for c in cnt.keys():\n",
    "                    if count[i][c]<cnt[c]:\n",
    "                        flag=False\n",
    "                        break\n",
    "                if flag:\n",
    "                    break\n",
    "            return flag\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            if state==0:\n",
    "                return 0\n",
    "            else:\n",
    "                res=float(\"inf\")\n",
    "                sub=state\n",
    "                while sub:\n",
    "                    sub=(sub-1)&state\n",
    "                    tmp=state^sub\n",
    "                    if check(tmp):\n",
    "                        res=min(res,dfs(sub)+1)\n",
    "                return res\n",
    "        res=dfs((1<<m)-1) \n",
    "        return -1 if res==float(\"inf\") else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, words: List[str], target: str) -> int:\n",
    "        st=set(target)\n",
    "        n=len(words)\n",
    "        count=[[0]*26 for _ in range(n)]\n",
    "        for i,w in enumerate(words):\n",
    "            for c in w:\n",
    "                count[i][ord(c)-ord(\"a\")]+=1\n",
    "        m=len(target)\n",
    "        @cache\n",
    "        def check(tmp):\n",
    "            cnt=[0]*26\n",
    "            for i,c in enumerate(str(bin(tmp))[2:][::-1]):\n",
    "                if c==\"1\":\n",
    "                    cnt[ord(target[i])-ord(\"a\")]+=1\n",
    "            #print(bin(tmp),cnt,str(bin(tmp))[2:][::-1])\n",
    "            for i in range(n):\n",
    "                for j in range(26):\n",
    "                    if cnt[j]>count[i][j]:\n",
    "                        break\n",
    "                else:\n",
    "                    return True\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            if state==0:\n",
    "                return 0\n",
    "            else:\n",
    "                res=float(\"inf\")\n",
    "                sub=state\n",
    "                while sub:\n",
    "                    sub=(sub-1)&state\n",
    "                    tmp=state^sub\n",
    "                    if check(tmp):\n",
    "                        res=min(res,dfs(sub)+1)\n",
    "                return res\n",
    "        res=dfs((1<<m)-1) \n",
    "        return -1 if res==float(\"inf\") else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        useful = []\n",
    "        visited = [False] * 26\n",
    "        cnt = [0] * 26\n",
    "        for c in target:\n",
    "            cnt[ord(c) - 97] += 1\n",
    "        for idx, sticker in enumerate(stickers):\n",
    "            tmp = 0\n",
    "            res = {}\n",
    "            letters = [0] * 26\n",
    "            for c in sticker:\n",
    "                letter = ord(c) - 97\n",
    "                visited[letter] = True\n",
    "                letters[letter] += 1\n",
    "            for i, n in enumerate(letters):\n",
    "                t = min(n, cnt[i])\n",
    "                if t > 0:\n",
    "                    tmp += t\n",
    "                    res[i] = t\n",
    "            if tmp > 0:\n",
    "                useful.append((tmp, res))\n",
    "\n",
    "        for i, n in enumerate(cnt):\n",
    "            if n > 0 and not visited[i]:\n",
    "                return -1\n",
    "\n",
    "        useful.sort(key=lambda tpl: tpl[0], reverse=True)\n",
    "\n",
    "\n",
    "        first = (0, tuple(cnt))\n",
    "        visited = {first}\n",
    "        queue = [first]\n",
    "        idx = 0\n",
    "        zeros = [0] * 26\n",
    "        while True:\n",
    "            val, tpl = queue[idx]\n",
    "            for _, use in useful:\n",
    "                li = list(tpl)\n",
    "                for i, c in use.items():\n",
    "                    li[i] = max(0, li[i] - c)\n",
    "                if li == zeros:\n",
    "                    return val + 1\n",
    "                now = val + 1, tuple(li)\n",
    "                if now not in visited:\n",
    "                    queue.append(now)\n",
    "                    visited.add(now)\n",
    "            idx += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        n = len(stickers)\n",
    "        sticker_chars = set(itertools.chain(*stickers))\n",
    "        target_chars = set(target)\n",
    "        if target_chars - sticker_chars:\n",
    "            return -1\n",
    "        stickers = [collections.Counter(sticker) for sticker in stickers]\n",
    "        target = collections.Counter(target)\n",
    "        stickers = [sticker & target for sticker in stickers]\n",
    "        pre_treat = []\n",
    "        for i in range(n):\n",
    "            if not any((stickers[i] & stickers[j]) == stickers[i] for j in range(n) if\n",
    "                       i != j and stickers[i] != stickers[j]):\n",
    "                pre_treat.append(stickers[i])\n",
    "        pre_treat.sort(key=len, reverse=True)\n",
    "        q = collections.deque()\n",
    "        q.append((target, 0))\n",
    "        while q:\n",
    "            next_q = collections.deque()\n",
    "            while q:\n",
    "                cur_target, steps = q.popleft()\n",
    "                if not cur_target:\n",
    "                    return steps\n",
    "                # tmp = deepcopy(cur_target)\n",
    "                tmp = cur_target\n",
    "                for c in pre_treat:\n",
    "                    if not tmp & c: continue\n",
    "                    next_target = tmp - c\n",
    "                    if not next_target: return steps + 1\n",
    "                    next_q.append((next_target, steps + 1))\n",
    "            q = next_q\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isRestEmpty(rest): #检查aims是否为空\n",
    "    if rest == []:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "def isHaveSame(rest, sticker): \n",
    "    \n",
    "    for i in rest:\n",
    "        index = ord(i)-ord('a')\n",
    "        if sticker[index]!=0:\n",
    "            return True\n",
    "    return False\n",
    "    \n",
    "def minus(rest, sticker):\n",
    "    count = 0\n",
    "    \n",
    "    sticker1 = sticker.copy()\n",
    "    while count < len(rest):\n",
    "        #print(i)\n",
    "        \n",
    "        word = rest[count]\n",
    "        \n",
    "        index = ord(word)-ord('a')\n",
    "        if sticker1[index]!=0:\n",
    "            sticker1[index] -= 1\n",
    "            rest.pop(count)\n",
    "        else:\n",
    "            count += 1\n",
    "    \n",
    "def process(rest, index, stickers,dp):\n",
    "    \n",
    "    key = ''.join(rest)\n",
    "    \n",
    "    if key in dp[index].keys():\n",
    "        return dp[index][key]\n",
    "\n",
    "    if isRestEmpty(rest):\n",
    "        return 0\n",
    "    \n",
    "    #print(rest)\n",
    "    \n",
    "    \n",
    "    \n",
    "    if index == len(stickers):\n",
    "        dp[index][key] = float('inf')\n",
    "        return float('inf')\n",
    "       \n",
    "        \n",
    "    if isHaveSame(rest, stickers[index]) == 0:\n",
    "        v = process(rest, index + 1, stickers,dp)\n",
    "    else:\n",
    "        \n",
    "        \n",
    "      \n",
    "        rest1 = rest.copy()\n",
    "        rest2 = rest.copy()\n",
    "        p1 = process(rest, index + 1, stickers,dp)\n",
    "       \n",
    "        \n",
    "        rest = rest1\n",
    "      \n",
    "        minus(rest, stickers[index])\n",
    "       \n",
    "        p2 = 1 + process(rest, index, stickers,dp)\n",
    "        rest = rest2\n",
    "    \n",
    "        v = min(p1, p2)\n",
    "    dp[index][key] = v\n",
    "    return v\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        stickers1 = []\n",
    "\n",
    "        aim2 = sorted(target)\n",
    "\n",
    "        for i in stickers:\n",
    "            #print(i)\n",
    "            sticker = [0] * 26\n",
    "            for j in i:\n",
    "                index = ord(j)-ord('a')\n",
    "                sticker[index] = sticker[index] + 1\n",
    "            stickers1.append(sticker)\n",
    "\n",
    "        aims = [0] * 26\n",
    "        for i in target:\n",
    "            index = ord(i) - ord('a')\n",
    "            aims[index] = aims[index] + 1\n",
    "\n",
    "        dp = []\n",
    "        for i in range(len(stickers)+1):\n",
    "            dp.append(dict())\n",
    "        ans = process(aim2,0,stickers1,dp)\n",
    "        \n",
    "        #print(len(dp))\n",
    "        if ans == float('inf'):\n",
    "            return -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        Alpha=[chr(i) for i in range(ord('a'),ord('z')+1)]\n",
    "        def str_to_int(target: str) -> int:             #将str压缩成一个整数，整数每四位代表某个字符(a-z)出现次数\n",
    "            target=Counter(target)\n",
    "            res,p=0,0\n",
    "            for c in Alpha:\n",
    "                res=res^(target[c]<<p)\n",
    "                p+=4\n",
    "            return res\n",
    "        \n",
    "        def sub(a: int, b: int) -> int:\n",
    "            x=0b1111\n",
    "            res=0\n",
    "            for i in range(26):\n",
    "                ta,tb=a&x,b&x\n",
    "                if ta>tb:\n",
    "                    res=res^(ta-tb)\n",
    "                x=x<<4\n",
    "            return res\n",
    "\n",
    "        def dfs(index: int, target: int) -> int:\n",
    "            if not target:\n",
    "                return 0\n",
    "            elif index<0:\n",
    "                return float('inf')\n",
    "            elif target in Map[index]:\n",
    "                return Map[index][target]\n",
    "            cnt,res=0,dfs(index-1,target)\n",
    "            temp=target\n",
    "            while (temp2:=sub(temp,stickers[index]))!=temp:\n",
    "                temp=temp2\n",
    "                cnt+=1\n",
    "                res=min(res,cnt+dfs(index-1,temp))\n",
    "            Map[index][target]=res\n",
    "            return res\n",
    "\n",
    "        n=len(stickers)\n",
    "        target=str_to_int(target)\n",
    "        Map=[{}for i in range(n)]\n",
    "        for i in range(n):\n",
    "            stickers[i]=str_to_int(stickers[i])\n",
    "        ans=dfs(n-1,target)\n",
    "        return ans if ans!=float('inf') else -1\n",
    "'''\n",
    "法一 dp+记忆化搜索\n",
    "小写英文字母只有26种，可以用长26的list表示每个单词的各个字母有几个。\n",
    "\n",
    "\n",
    "法二 dp+记忆化搜索+状态压缩\n",
    "因为每个单词都小于10个字母，且target至多只有15个字母，\n",
    "即可以使用4bit描述一种字母需要几个共26*4bit，13B，比用26个int好多了\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers, target: str) -> int:\n",
    "        from collections import Counter\n",
    "        from collections import defaultdict\n",
    "        from functools import lru_cache\n",
    "        n = len(target)\n",
    "        data = Counter(target)\n",
    "        stickers = list(set(''.join(i for i in j if i in data) for j in stickers))\n",
    "        data1 = [Counter(i) for i in stickers]\n",
    "\n",
    "        def ok(i):\n",
    "            if all(k not in data for k in data1[i]):\n",
    "                return False\n",
    "            if any(all(data1[j][k] > data1[i][k] for k in data1[i]) for j in range(0, len(data1)) if j != i):\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        stickers = [Counter(stickers[i]) for i in range(0, len(stickers)) if ok(i)]\n",
    "\n",
    "        dic = defaultdict(list)\n",
    "        tmp = 1\n",
    "        for c in data:\n",
    "            for i in range(0, data[c]):\n",
    "                dic[c].append(tmp)\n",
    "                tmp = tmp << 1\n",
    "        start = 0\n",
    "        end = 2 ** len(target) - 1\n",
    "\n",
    "        # print(stickers)\n",
    "        # print(start)\n",
    "        # print(bin(end))\n",
    "        # print(target)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check(i, stat):\n",
    "            d = stickers[i]\n",
    "            tmp = 1\n",
    "            while stat & tmp > 0:\n",
    "                tmp = tmp << 1\n",
    "            for k in d:\n",
    "                if any(i == tmp for i in dic[k]):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def transfer(stat, i):\n",
    "            d = stickers[i]\n",
    "            for k in d:\n",
    "                ctx = d[k]\n",
    "                for i in dic[k]:\n",
    "                    tmp = stat | i\n",
    "                    if tmp > stat:\n",
    "                        stat=tmp\n",
    "                        ctx-=1\n",
    "                        if ctx==0:\n",
    "                            break\n",
    "            return stat\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def recur(stat):\n",
    "            # print(stat)\n",
    "            if stat == end:\n",
    "                return 0\n",
    "            return min((recur(transfer(stat,d))+1 for d in range(0,len(stickers)) if check(d,stat)),default=-100)\n",
    "\n",
    "        tmp = recur(start)\n",
    "        return tmp if tmp>0 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        Alpha=[chr(i) for i in range(ord('a'),ord('z')+1)]\n",
    "        def str_to_int(target: str) -> int:             #将str压缩成一个整数，整数每四位代表某个字符(a-z)出现次数\n",
    "            target=Counter(target)\n",
    "            res,p=0,0\n",
    "            for c in Alpha:\n",
    "                res=res^(target[c]<<p)\n",
    "                p+=4\n",
    "            return res\n",
    "        \n",
    "        def sub(a: int, b: int) -> int:\n",
    "            cntN[1]+=1\n",
    "            x=15\n",
    "            res=0\n",
    "            for i in range(26):\n",
    "                ta,tb=a&x,b&x\n",
    "                if ta>tb:\n",
    "                    res=res^(ta-tb)\n",
    "                x=x<<4\n",
    "            return res\n",
    "\n",
    "        def dfs(index: int, target: int) -> int:\n",
    "            cntN[0]+=1\n",
    "            if not target:\n",
    "                return 0\n",
    "            elif index<0:\n",
    "                return float('inf')\n",
    "            elif target in Map[index]:\n",
    "                return Map[index][target]\n",
    "            cntN[2]+=1\n",
    "            cnt,res=0,dfs(index-1,target)\n",
    "            temp=target\n",
    "            while (temp2:=sub(temp,stickers[index]))!=temp:\n",
    "                temp=temp2\n",
    "                cnt+=1\n",
    "                res=min(res,cnt+dfs(index-1,temp))\n",
    "            Map[index][target]=res\n",
    "            return res\n",
    "\n",
    "        cntN=[0]*3\n",
    "        n=len(stickers)\n",
    "        target=str_to_int(target)\n",
    "        Map=[{}for i in range(n)]\n",
    "        for i in range(n):\n",
    "            stickers[i]=str_to_int(stickers[i])\n",
    "        ans=dfs(n-1,target)\n",
    "        return ans if ans!=float('inf') else -1\n",
    "'''\n",
    "法一 dp+记忆化搜索\n",
    "小写英文字母只有26种，可以用长26的list表示每个单词的各个字母有几个。\n",
    "\n",
    "\n",
    "法二 dp+记忆化搜索+状态压缩\n",
    "因为每个单词都小于10个字母，且target至多只有15个字母，\n",
    "即可以使用4bit描述一种字母需要几个共26*4bit，13B，比用26个int好多了\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "def isRestEmpty(rest):\n",
    "    return max(rest) == 0\n",
    "\n",
    "def isHaveSame(rest,sticker):\n",
    "    maxV=0\n",
    "    for i in range(26):\n",
    "        maxV = max(maxV,rest[i] and sticker[i])\n",
    "    return maxV\n",
    "\n",
    "def minus(rest,sticker):\n",
    "    for i in range(26):\n",
    "        isHaveSame = rest[i] and sticker[i]\n",
    "        if isHaveSame:\n",
    "            differ = rest[i] - sticker[i]\n",
    "            if differ <=0:\n",
    "                rest[i]=0\n",
    "            else:\n",
    "                rest[i]=differ\n",
    "\n",
    "def process(rest, index, stickers, dp):\n",
    "\n",
    "    b=[str(i) for i in rest]\n",
    "    key = ''.join(b)\n",
    "\n",
    "    if key in dp[index].keys():\n",
    "        return dp[index][key]\n",
    "    \n",
    "    if isRestEmpty(rest):\n",
    "        dp[index][key]=0\n",
    "        return 0\n",
    "    \n",
    "    if index == len(stickers):\n",
    "        dp[index][key] = float('inf')\n",
    "        return float('inf')\n",
    "\n",
    "    if isHaveSame(rest,stickers[index]) == 0:\n",
    "        v = process(rest, index+1, stickers, dp)\n",
    "    else:\n",
    "        rest1 = rest.copy()\n",
    "        rest2 = rest.copy()\n",
    "        p1 = process(rest, index+1, stickers, dp)\n",
    "\n",
    "        rest = rest1\n",
    "        minus(rest, stickers[index])\n",
    "        p2 = 1+process(rest,index,stickers,dp)\n",
    "        rest = rest2\n",
    "\n",
    "        v = min(p1,p2)\n",
    "    dp[index][key] = v\n",
    "    return v\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        tzs = []\n",
    "        for i in stickers:\n",
    "            tz = [0]*26\n",
    "            for j in i:\n",
    "                index = ord(j)-ord('a')\n",
    "                tz[index]=tz[index]+1\n",
    "            tzs.append(tz)\n",
    "        aims = [0]*26\n",
    "        for i in target:\n",
    "            index = ord(i)-ord('a')\n",
    "            aims[index]=aims[index]+1\n",
    "\n",
    "        dp=[]\n",
    "        for i in range(len(stickers)+1):\n",
    "            dp.append(dict())\n",
    "\n",
    "        ans = process(aims,0,tzs,dp)\n",
    "        if math.isinf(ans):\n",
    "            return -1\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        cnt = [Counter(s) for s in stickers]\n",
    "        dp = [[float('inf')]*(1<<len(target)) for _ in range(len(stickers))]\n",
    "        def check(i, c):\n",
    "            _i, d = i, defaultdict(int)\n",
    "            for k in range(len(target)):\n",
    "                if _i&(1<<k) == 0 and c[target[k]] > 0:\n",
    "                    _i += 1<<k\n",
    "                    c[target[k]] -= 1\n",
    "                    d[target[k]] += 1\n",
    "            for k, v in d.items():\n",
    "                c[k] += v\n",
    "            return _i\n",
    "        dp[0][0] = 0\n",
    "        t = p = 0\n",
    "        while True:\n",
    "            _p = check(p, cnt[0])\n",
    "            t += 1\n",
    "            if p == _p: break\n",
    "            dp[0][_p] = t\n",
    "            p = _p\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(len(dp[i])):\n",
    "                if dp[i-1][j] == float('inf'): continue\n",
    "                t, p = 0, j\n",
    "                dp[i][p] = min(dp[i][p], dp[i-1][p])\n",
    "                while True:\n",
    "                    _p = check(p, cnt[i])\n",
    "                    t += 1\n",
    "                    if p == _p: break\n",
    "                    dp[i][_p] = min(dp[i][_p], dp[i-1][j]+t)\n",
    "                    p = _p\n",
    "        if dp[-1][-1] == float('inf'):\n",
    "            return -1\n",
    "        return dp[-1][-1]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        ans = float(inf)\n",
    "        candidates = [sticker for sticker in stickers if set(sticker).intersection(set(target)) != set()]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(target_counter, times):\n",
    "            nonlocal ans\n",
    "            # 如果target_counter已经为空，说明符合条件，尝试更新最小的次数\n",
    "            target_counter = list(target_counter)\n",
    "            if sum(target_counter) == 0:\n",
    "                ans = min(ans, times)\n",
    "                return\n",
    "\n",
    "            # 否则，从有效的候选集合中逐个尝试\n",
    "            for candidate in candidates:\n",
    "                new_counter = target_counter[:]\n",
    "                for c in candidate:\n",
    "                    if c in target and new_counter[ord(c)-ord('a')]>0:\n",
    "                        new_counter[ord(c)-ord('a')] -= 1\n",
    "\n",
    "                if new_counter != target_counter:\n",
    "                    dfs(tuple(new_counter), times+1)\n",
    "\n",
    "        target_counter = [0 for _ in range(26)]\n",
    "        for c in target:\n",
    "           target_counter[ord(c)-ord('a')] += 1\n",
    "        target_counter = tuple(target_counter)\n",
    "        \n",
    "        dfs(target_counter, 0)\n",
    "        \n",
    "        if ans == float(inf):\n",
    "            return -1\n",
    "        else: return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import ceil\n",
    "class Solution:\n",
    "\tdef minStickers(self,stickers,target):\n",
    "\t\tt1,t2=set(),set(target)\n",
    "\t\tfor i in stickers:\n",
    "\t\t\tt1|=set(i)\n",
    "\t\tif t2-t1:\n",
    "\t\t\treturn -1\n",
    "\t\thas=[]\n",
    "\t\tMAX=float(\"inf\")\n",
    "\t\tsize=len(stickers)\n",
    "\t\tstickers.sort(key=len)\n",
    "\t\tfor i in stickers+[target]:\n",
    "\t\t\ttmp=[0]*26\n",
    "\t\t\tfor j in i:\n",
    "\t\t\t\ttmp[ord(j)-97]+=1\n",
    "\t\t\thas.append(tmp)\n",
    "\t\tmemo={(i,(0,)*26):0 for i in range(size+1)}\n",
    "\t\tdef helper(i,need):\n",
    "\t\t\t# print(i,need)\n",
    "\t\t\tif memo.get((i,need),None) is None:\n",
    "\t\t\t\tif i==size:\n",
    "\t\t\t\t\treturn MAX\n",
    "\t\t\t\ttans=helper(i+1,need)\n",
    "\t\t\t\tj=i\n",
    "\t\t\t\ttmpNeed=list(need)\n",
    "\t\t\t\tfor k in range(1,max(ceil(x/y) for x,y in zip(need,has[j]) if y)+1):\n",
    "\t\t\t\t\tfor p,q in enumerate(has[j]):\n",
    "\t\t\t\t\t\ttmpNeed[p]=max(tmpNeed[p]-q,0)\n",
    "\t\t\t\t\ttans=min(tans,helper(j+1,tuple(tmpNeed))+k)\n",
    "\t\t\t\tmemo[(i,need)]=tans\n",
    "\t\t\treturn memo[(i,need)]\n",
    "\t\treturn helper(0,tuple(has.pop()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        arr = []\n",
    "        for s in stickers:\n",
    "            v = [0]*26\n",
    "            for i in s:\n",
    "                v[ord(i)-ord(\"a\")] += 1\n",
    "            arr.append(tuple(v))\n",
    "\n",
    "        tv = [0]*26\n",
    "        for i in target:\n",
    "            tv[ord(i)-ord(\"a\")] += 1\n",
    "        \n",
    "        def minus(a,b):\n",
    "            v = [0]*26\n",
    "            flag = False\n",
    "            for i in range(26):\n",
    "                if a[i] >= b[i]:\n",
    "                    v[i] = a[i] - b[i]\n",
    "                else:\n",
    "                    v[i] = 0\n",
    "            ans = tuple(v)\n",
    "            if ans == a:\n",
    "                return None,False\n",
    "            else:\n",
    "                return ans,True\n",
    "\n",
    "        zv = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)\n",
    "        def equal(a,b):\n",
    "            for i in range(26):\n",
    "                if a[i] != b[i]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(n,tv):\n",
    "            if n == -1:\n",
    "                if equal(tv, zv):\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "            ans = inf\n",
    "            ans = min(ans,dp(n-1,tv))\n",
    "            i = 1\n",
    "            while tv != zv:\n",
    "                tv,f = minus(tv,arr[n])\n",
    "                if f:\n",
    "                    ans = min(ans,dp(n-1,tv)+i)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    \n",
    "                    break\n",
    "            return ans\n",
    "            \n",
    "        ans = dp(len(stickers)-1, tuple(tv))\n",
    "        if ans == inf:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "\n",
    "        c = Counter(target)\n",
    "        keys = list(c.keys())\n",
    "        values = list(c.values())\n",
    "\n",
    "        stick2 = []\n",
    "        for word in stickers:\n",
    "            use = False\n",
    "            c = Counter(word)\n",
    "            v = []\n",
    "            for key in keys:\n",
    "                if c[key] > 0: use = True\n",
    "                v.append(c[key])\n",
    "            if use: stick2.append(v)\n",
    "\n",
    "        space = -1\n",
    "        def log(func):\n",
    "            def wrapper(*args):\n",
    "                nonlocal space\n",
    "                space += 1\n",
    "                res = func(*args)\n",
    "                print(space*\"-\", *args, \":\", res)\n",
    "                space -= 1\n",
    "                return res\n",
    "            return wrapper\n",
    "\n",
    "        #@log\n",
    "        @cache\n",
    "        def solve(need, i):\n",
    "            if i == len(stick2):\n",
    "                if sum(need) > 0: return float(\"inf\")\n",
    "                return 0\n",
    "            r = solve(need, i+1)\n",
    "            n = list(need)\n",
    "            use = True\n",
    "            useCount = 0\n",
    "            while use:\n",
    "                use = False\n",
    "                useCount += 1\n",
    "                for k in range(len(keys)):\n",
    "                    if n[k] > 0 and stick2[i][k] > 0: \n",
    "                        use = True\n",
    "                        n[k] = max(n[k]-stick2[i][k], 0)\n",
    "                if use:\n",
    "                    r = min(solve(tuple(n), i+1)+useCount, r)\n",
    "            return r\n",
    "        \n",
    "        #print(keys)\n",
    "        res = solve(tuple(values), 0) \n",
    "        if res == float(\"inf\"): return -1\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        if len(target)==0:\n",
    "            return 0\n",
    "        dict_target=defaultdict(int)\n",
    "        for g in target:\n",
    "            dict_target[g]+=1\n",
    "        table=defaultdict(int)\n",
    "        res=self.f(stickers,dict_target,0,table)\n",
    "        return res if res!=math.inf else -1\n",
    "    def f(self,stickers,dict_target:defaultdict,cur,table):\n",
    "        dict_value=[i for i in dict_target.values()]\n",
    "        dict_value.append(cur)\n",
    "        key = tuple(dict_value)\n",
    "        if key in table:\n",
    "            return table[key]\n",
    "        if sum(dict_target.values())==0:\n",
    "            return 0\n",
    "        elif cur==len(stickers):\n",
    "            return math.inf\n",
    "\n",
    "        res=self.f(stickers,dict_target.copy(),cur+1,table)\n",
    "        tf=False\n",
    "        for g in stickers[cur]:\n",
    "            if g in dict_target and dict_target[g]!=0:\n",
    "                dict_target[g]-=1\n",
    "                if dict_target[g]!=0:\n",
    "                    tf=True\n",
    "        res=min(res,1+self.f(stickers,dict_target.copy(),cur+1,table))\n",
    "        if tf:\n",
    "            res=min(res,1+self.f(stickers,dict_target.copy(),cur,table))\n",
    "\n",
    "        table[key]=res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "import math\n",
    "class Solution:\n",
    "    # 暴力 dfs 遍历，我的朋友\n",
    "    # dfs(mask)，也就是去找能够组成 mask 的 sticker 数量，注意这里都是小写字符，所以本质上可以直接用一个长度为 26 的向量来表示每一个 sticker 能够贡献的字符数\n",
    "    # 对每一个 mask 都需要将所有的 sticker 遍历一遍，剩下的进入下一个 dfs\n",
    "\n",
    "    # 但是注意先删掉 a 和先删掉 b 本质是一样的，也就是说可以先对所有的 stickers 进行排序，删第 i 个结束后可以再删一遍第 i 个或者进入第 i+1 个\n",
    "    # 同时用一个 state 字典，key 为当前的 mask，value 为达到当前的 mask 需要的最小贴纸数，如果已经超过了就停止\n",
    "\n",
    "    def dfs(self, mask, cnt, i):\n",
    "        if i == self.n: return\n",
    "        if cnt >= self.ans: return\n",
    "        st = self.stickers_dict[self.stickers[i]]\n",
    "        mask0 = mask-st\n",
    "        mask0[mask0<0] = 0\n",
    "        if sum(mask0) == 0: self.ans = min(self.ans, cnt+1); return\n",
    "        \n",
    "        self.dfs(mask, cnt, i+1)\n",
    "        if not (mask == mask0).all():   \n",
    "            mask02 = 0\n",
    "            for pos in range(26):   mask02 += mask0[pos]*(2**pos)\n",
    "            if mask02 in self.state:    \n",
    "                if self.state[mask02]<=(cnt+1): return\n",
    "            self.state[mask02] = cnt+1\n",
    "            self.dfs(mask0, cnt+1, i)\n",
    "            self.dfs(mask0, cnt+1, i+1)\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        self.stickers_dict = {}\n",
    "        for st in stickers:\n",
    "            temp = [0]*26\n",
    "            for s in st:    temp[ord(s)-ord('a')]+=1\n",
    "            self.stickers_dict[st] = np.array(temp)\n",
    "        self.stickers = stickers\n",
    "        self.n = len(stickers)\n",
    "\n",
    "        self.ans = float('inf')\n",
    "        self.state = {}\n",
    "        temp = [0]*26\n",
    "        for st in target:   temp[ord(st)-ord('a')]+=1\n",
    "        self.dfs(np.array(temp),0,0)\n",
    "        return -1 if math.isinf(self.ans) else self.ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minStickers(self, stickers, target):\n",
    "        \"\"\"\n",
    "        求解要拼接成指定的target单词, 所需要的最少贴纸数\n",
    "        Args:\n",
    "            stickers (list[str]):\n",
    "            target (str):\n",
    "        returns  (int):\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if stickers == None or len(stickers) == 0 or target == None:\n",
    "            return -1 \n",
    "        \n",
    "        if len(target) == 0:\n",
    "            return 0 \n",
    "        \n",
    "        #为方便后续处理, 统计各张贴纸所含有的字母个数\n",
    "        stickers_cnts = [Counter(sticker) for sticker in stickers]\n",
    "        dp = {}\n",
    "\n",
    "        ans = self.process(stickers_cnts, 0, target, dp)\n",
    "        if ans == float(\"inf\"):\n",
    "            return -1 \n",
    "        \n",
    "        return ans \n",
    "    \n",
    "    def process(self, stickers_cnts, index, cur_left_chars, dp):\n",
    "        \"\"\"\n",
    "        记忆化求解在当前所剩单词(cur_left_chars)的情况下, 所需要的最少贴纸数 \n",
    "        Args:\n",
    "            stickers_cnts (list[dict[char: int]]): 各张贴纸所含的字母情况\n",
    "            index (int): 当前待选择贴纸索引\n",
    "            cur_left_chars (str): 还需要拼接的字符\n",
    "            dp (dict[str: int]): 记录各个剩余字符所需要的最少字符\n",
    "        returns (int): 剩余字符所需要的单词数\n",
    "        \"\"\"\n",
    "        #若已经访问过当前状态, 直接返回结果\n",
    "        if dp.__contains__(str(index) + cur_left_chars):\n",
    "            return dp[str(index) + cur_left_chars]\n",
    "\n",
    "        #递归出口, 剩余字符为空字符\n",
    "        if cur_left_chars == '':\n",
    "            return 0 \n",
    "            \n",
    "        #若无法拼接成功, 返回-1\n",
    "        if index == len(stickers_cnts):\n",
    "            if cur_left_chars != '':\n",
    "                return -1 \n",
    "            else:\n",
    "                return 0 \n",
    "\n",
    "        #对当前贴纸有两种选择, case1. 不选择当前贴纸\n",
    "        no_selected = self.process(stickers_cnts, index + 1, cur_left_chars, dp) \n",
    "        if no_selected == -1:\n",
    "            no_selected = float(\"inf\")\n",
    "\n",
    "        flag = False #用于剪枝, 若当前贴纸不含有剩余字符的字母, 直接跳过不需要执行case2\n",
    "        for c in cur_left_chars:\n",
    "            if stickers_cnts[index].__contains__(c):\n",
    "                flag = True \n",
    "                break \n",
    "        \n",
    "        selected = float(\"inf\")\n",
    "\n",
    "        if flag:\n",
    "            #case2. 选择当前贴纸\n",
    "            next_left_chars = self.deleteSticker(stickers_cnts[index], cur_left_chars)\n",
    "            next_value = self.process(stickers_cnts, index, next_left_chars, dp)\n",
    "            \n",
    "            if next_value != -1:\n",
    "                selected = 1 + next_value\n",
    "\n",
    "        ans = min(selected, no_selected)\n",
    "        \n",
    "        #将结果记录下来\n",
    "        dp[str(index) + cur_left_chars] = ans    \n",
    "\n",
    "        return ans \n",
    "\n",
    "    def deleteSticker(self, stickers_cnt, cur_left_char):\n",
    "        \"\"\"\n",
    "        将当前字符减去贴纸之中存在的有效字符, 得到新的剩余字符\n",
    "        Args:\n",
    "            stickers_cnt (dict[char: int]): 该张贴纸所含有的各个字符数\n",
    "            cur_left_char (str): 当前剩余的字符\n",
    "        returns (str): 拼接该贴纸后所剩余的字符\n",
    "        \"\"\"\n",
    "        for c in stickers_cnt.keys():\n",
    "            cur_left_char = cur_left_char.replace(c, '', stickers_cnt[c])\n",
    "\n",
    "        return cur_left_char \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        ll = list(set(target))\n",
    "        mp = {c: i for i, c in enumerate(ll)}\n",
    "        m = len(ll)\n",
    "        \n",
    "        def count(w):\n",
    "            ret = Counter()\n",
    "            for c in w:\n",
    "                if c in mp:\n",
    "                    ret[mp[c]] += 1\n",
    "            return ret\n",
    "\n",
    "        tar = count(target)\n",
    "        sks = [cur for w in stickers if (cur := count(w))]\n",
    "        if len(tar) > len(reduce(add, sks, Counter())):\n",
    "            return -1\n",
    "        n = len(sks)\n",
    "\n",
    "        cc = {}\n",
    "\n",
    "        ans = m\n",
    "        def dfs(i, cnt, tot=0):\n",
    "            nonlocal ans\n",
    "            if not cnt:\n",
    "                ans = tot\n",
    "                return 0\n",
    "            if tot >= ans:\n",
    "                return 100\n",
    "            if i == n:\n",
    "                return 100\n",
    "            key = tuple([cnt[i] for i in range(m)])\n",
    "            if (i, key) in cc:\n",
    "                return cc[(i, key)]\n",
    "\n",
    "            ret = dfs(i + 1, cnt, tot)\n",
    "            c2 = cnt\n",
    "            for x in range(1, 100):\n",
    "                c2 = c2 - sks[i]\n",
    "                if c2 == cnt:\n",
    "                    break\n",
    "                ret = min(ret, dfs(i + 1, c2, tot + x) + x)\n",
    "                cnt = c2\n",
    "            cc[(i, key)] = ret\n",
    "            return ret\n",
    "\n",
    "        return dfs(0, tar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, a: List[str], target: str) -> int:\n",
    "        n = len(a)\n",
    "        def s2t(s):\n",
    "            c = Counter(s)\n",
    "            return tuple(c[chr(ord('a') + i)] for i in range(26))\n",
    "        at = [s2t(s) for s in a]\n",
    "        tt = s2t(target)\n",
    "        if any(all(t[i] == 0 for t in at) for i in range(26) if tt[i]): return -1\n",
    "        at = [tuple(t[i] for i in range(26) if tt[i]) for t in at]\n",
    "        tt = tuple(tt[i] for i in range(26) if tt[i])\n",
    "        @cache\n",
    "        def dfs(i, tt):\n",
    "            if sum(tt) == 0: return 0\n",
    "            if i == n: return inf\n",
    "            mn = dfs(i + 1, tt)\n",
    "            j = 0\n",
    "            ati = at[i]\n",
    "            while sum(tt):\n",
    "                ntt = tuple(max(x - y, 0) for x, y in zip(tt, ati))\n",
    "                if ntt == tt: break\n",
    "                tt = ntt\n",
    "                j += 1\n",
    "                mn = min(mn, j + dfs(i + 1, tt))\n",
    "            return mn\n",
    "        res = dfs(0, tt)\n",
    "        return res if res < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStickers(self, stickers: List[str], target: str) -> int:\n",
    "        t = [0] * 26\n",
    "        n = len(stickers)\n",
    "        for s in target:\n",
    "            t[ord(s) - ord('a')] += 1\n",
    "\n",
    "        words = []\n",
    "        sets = []\n",
    "        for word in stickers:\n",
    "            w = [0] * 26\n",
    "            for s in word:\n",
    "                w[ord(s) - ord('a')] += 1\n",
    "            words.append(w)\n",
    "            sets.append(set(i for i in range(26) if w[i] > 0))\n",
    "\n",
    "        @cache\n",
    "        def dfs(begin, tar):\n",
    "            if sum(1 for i in range(26) if tar[i] > 0) == 0:\n",
    "                return 0\n",
    "            if begin == n:\n",
    "                return math.inf\n",
    "            s1 = set(i for i in range(26) if tar[i] > 0)\n",
    "            if s1.isdisjoint(sets[begin]):\n",
    "                return dfs(begin + 1, tar)\n",
    "            rem = tuple(max(0, tar[i] - words[begin][i]) for i in range(26))\n",
    "            return min(1 + dfs(begin, rem), dfs(begin + 1, tar))\n",
    "\n",
    "        mi = dfs(0, tuple(t))\n",
    "        return -1 if mi == math.inf else mi "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
